{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Dungeon Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: calculateMinimumHP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #地下城游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<style type=\"text/css\">table.dungeon, .dungeon th, .dungeon td {\n",
    "  border:3px solid black;\n",
    "}\n",
    "\n",
    " .dungeon th, .dungeon td {\n",
    "    text-align: center;\n",
    "    height: 70px;\n",
    "    width: 70px;\n",
    "}\n",
    "</style>\n",
    "<p>恶魔们抓住了公主并将她关在了地下城&nbsp;<code>dungeon</code> 的 <strong>右下角</strong> 。地下城是由 <code>m x n</code> 个房间组成的二维网格。我们英勇的骑士最初被安置在 <strong>左上角</strong> 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。</p>\n",
    "\n",
    "<p>骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。</p>\n",
    "\n",
    "<p>有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为<em>负整数</em>，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 <em>0</em>），要么包含增加骑士健康点数的魔法球（若房间里的值为<em>正整数</em>，则表示骑士将增加健康点数）。</p>\n",
    "\n",
    "<p>为了尽快解救公主，骑士决定每次只 <strong>向右</strong> 或 <strong>向下</strong> 移动一步。</p>\n",
    "\n",
    "<p>返回确保骑士能够拯救到公主所需的最低初始健康点数。</p>\n",
    "\n",
    "<p><strong>注意：</strong>任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/13/dungeon-grid-1.jpg\" style=\"width: 253px; height: 253px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>如果骑士遵循最佳路径：右 -&gt; 右 -&gt; 下 -&gt; 下 ，则骑士的初始健康点数至少为 7 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dungeon = [[0]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == dungeon.length</code></li>\n",
    "\t<li><code>n == dungeon[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 200</code></li>\n",
    "\t<li><code>-1000 &lt;= dungeon[i][j] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [dungeon-game](https://leetcode.cn/problems/dungeon-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [dungeon-game](https://leetcode.cn/problems/dungeon-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[-2,-3,3],[-5,-10,1],[10,30,-5]]', '[[0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        \n",
    "        R,C = len(dungeon),len(dungeon[0])\n",
    "        dp = [[ 0 for c in range(C)] for r in range(R)]\n",
    "        for r in range(R-1,-1,-1):\n",
    "            for c in range(C-1,-1,-1):\n",
    "                if c==C-1 and r==R-1:\n",
    "                    dp[r][c] = max(1,1-dungeon[r][c])\n",
    "                else:\n",
    "                    valRight = float('inf') if c==C-1 else dp[r][c+1]\n",
    "                    valDown = float('inf') if r==R-1 else dp[r+1][c]\n",
    "                    dp[r][c] = max(1, min(valRight,valDown)-dungeon[r][c])\n",
    "        return dp[0][0]\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: 'List[List[int]]') -> 'int':\n",
    "        m = len(dungeon)\n",
    "        n = len(dungeon[0])\n",
    "        memo = dungeon\n",
    "\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if i == m - 1 and j == n - 1:\n",
    "                    memo[i][j] = max(1, 1 - memo[i][j])\n",
    "                elif i == m - 1:\n",
    "                    memo[i][j] = max(1, memo[i][j + 1] - memo[i][j])\n",
    "                elif j == n - 1:\n",
    "                    memo[i][j] = max(1, memo[i + 1][j] - memo[i][j])\n",
    "                else:\n",
    "                    memo[i][j] = min(memo[i + 1][j], memo[i][j + 1]) - memo[i][j]\n",
    "                    memo[i][j] = max(1, memo[i][j])\n",
    "        # print(memo)\n",
    "        return memo[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon):\n",
    "        \"\"\"\n",
    "        :type dungeon: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        result = [[99999999 for _ in range(len(dungeon[0])+1)] for _ in range(len(dungeon)+1)]\n",
    "        result[len(dungeon)][len(dungeon[0])-1] = 1\n",
    "        result[len(dungeon)-1][len(dungeon[0])] = 1\n",
    "        for i in range(len(dungeon)-1, -1, -1):\n",
    "            for j in range(len(dungeon[0])-1, -1, -1):\n",
    "                result[i][j] = max(1,min(result[i+1][j], result[i][j+1]) - dungeon[i][j])\n",
    "        return result[0][0]\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: 'List[List[int]]') -> 'int':\n",
    "        if not dungeon or not dungeon[0]:\n",
    "            return 1\n",
    "        m,n=len(dungeon),len(dungeon[0])\n",
    "        dp=copy.deepcopy(dungeon)\n",
    "        dp[-1][-1]=min(dp[-1][-1],0)\n",
    "        for i in range(n-2,-1,-1):\n",
    "            dp[m-1][i]=min(dp[m-1][i+1]+dungeon[m-1][i],0)\n",
    "        for i in range(m-2,-1,-1):\n",
    "            dp[i][n-1]=min(dp[i+1][n-1]+dungeon[i][n-1],0)\n",
    "        for i in range(m-2,-1,-1):\n",
    "            for j in range(n-2,-1,-1):\n",
    "                dp[i][j]=min(dungeon[i][j]+max(dp[i+1][j],dp[i][j+1]),0)\n",
    "        return max(-dp[0][0]+1,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon):\n",
    "        \"\"\"\n",
    "        :type dungeon: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dp = []\n",
    "        N = len(dungeon[0])\n",
    "        M = len(dungeon)\n",
    "        for i in range(M):\n",
    "            dungeon[i] = dungeon[i][::-1]\n",
    "        dungeon = dungeon[::-1]\n",
    "\n",
    "        for i in range(M):\n",
    "            dp.append([0] * N)\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                if i > 0 and j > 0:\n",
    "                    tmp1 = max(1,dp[i - 1][j] - dungeon[i][j])\n",
    "                    tmp2 = max(1,dp[i][j - 1] - dungeon[i][j])\n",
    "                    if tmp1 < tmp2:\n",
    "                        dp[i][j] = tmp1\n",
    "                    else:\n",
    "                        dp[i][j] = tmp2\n",
    "                elif i == 0 and j > 0:\n",
    "                    dp[i][j] = max(1,dp[i][j - 1] - dungeon[i][j])\n",
    "                elif i > 0 and j == 0:\n",
    "                    dp[i][j] = max(1,dp[i - 1][j] - dungeon[i][j])\n",
    "                else:\n",
    "                    dp[0][0] = max(1,1 - dungeon[0][0])\n",
    "        return dp[-1][-1]\n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon):\n",
    "        \"\"\"\n",
    "        :type dungeon: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dp = [[(0, 0) for _ in dungeon[0]] for _ in dungeon]\n",
    "\n",
    "        dp[-1][-1] = (dungeon[-1][-1], dungeon[-1][-1])\n",
    "\n",
    "        for i in range(len(dungeon) - 2, -1, -1):\n",
    "            c1 = dp[i + 1][-1][1] + dungeon[i][-1]\n",
    "            dp[i][-1] = (dp[i + 1][-1][0] + dungeon[i][-1], min(dungeon[i][-1], c1, 0))\n",
    "\n",
    "        for j in range(len(dungeon[0]) - 2, -1, -1):\n",
    "            c2 = dp[-1][j + 1][1] + dungeon[-1][j]\n",
    "            dp[-1][j] = (dp[-1][j + 1][0] + dungeon[-1][j], min(dungeon[-1][j], c2, 0))\n",
    "\n",
    "        for i in range(len(dungeon) - 2, -1, -1):\n",
    "            for j in range(len(dungeon[0]) - 2, -1, -1):\n",
    "                c1 = dp[i + 1][j][1] + dungeon[i][j]\n",
    "                c2 = dp[i][j + 1][1] + dungeon[i][j]\n",
    "                if c1 > c2:\n",
    "                    dp[i][j] = (dp[i + 1][j][0] + dungeon[i][j], min(dungeon[i][j], c1, 0))\n",
    "                else:\n",
    "                    dp[i][j] = (dp[i][j + 1][0] + dungeon[i][j], min(dungeon[i][j], c2, 0))\n",
    "\n",
    "        return 1 - min(*dp[0][0], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon):\n",
    "        \"\"\"\n",
    "        :type dungeon: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cache = {}\n",
    "        def leastHP(x,y):\n",
    "            if (x,y) in cache:\n",
    "                return cache[(x,y)]\n",
    "            if x==len(dungeon)-1 and y==len(dungeon[0])-1:\n",
    "                cache[(x,y)] = max(-dungeon[x][y]+1,1)\n",
    "                return cache[(x,y)]\n",
    "            if x>=len(dungeon) or y>=len(dungeon[0]):\n",
    "                return 999999999999\n",
    "            bestroute = min(leastHP(x+1,y), leastHP(x,y+1))\n",
    "            \n",
    "            thisgrid = dungeon[x][y]\n",
    "            ret = max(bestroute - thisgrid, 1)\n",
    "            cache[(x,y)] = ret\n",
    "            return ret\n",
    "        \n",
    "        ret = leastHP(0,0)\n",
    "        print(cache)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon):\n",
    "        m,n = len(dungeon), len(dungeon[0])\n",
    "        dp = [sys.maxsize for _ in range(n+1)]\n",
    "        # dp[-1] = 1\n",
    "        dp[-2] = 1\n",
    "        for i in range(m-1, -1 , -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                dp[j] = max(1, min(dp[j], dp[j+1])-dungeon[i][j])\n",
    "            print(dp)\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        if not dungeon:\n",
    "            return \n",
    "        row = len(dungeon)\n",
    "        col = len(dungeon[0])\n",
    "        if row>=col:\n",
    "            more,less = row,col\n",
    "        else :\n",
    "            more,less = col,row\n",
    "        rowmore = more == row\n",
    "        dp = [sys.maxsize]*(less+1)\n",
    "        dp[-2] = 1\n",
    "        for j in range(more-1,-1,-1):\n",
    "            for i in range(less-1,-1,-1):              \n",
    "                dp[i] = max(1,min(dp[i+1],dp[i])-(dungeon[j][i] if rowmore else dungeon[i][j]))\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import product\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def calculateMinimumHP1(self, dungeon: List[List[int]]) -> int:\r\n",
    "        \"\"\"带备忘录的 dfs, Status:Succeed\"\"\"\r\n",
    "        m, n = len(dungeon), len(dungeon[0])\r\n",
    "        dp = [ [0] * n for i in range(m)]   # hp needed to arrive destination\r\n",
    "        dp[-1][-1] = max(1-dungeon[-1][-1], 1)\r\n",
    "        def is_valid_pos(pos):\r\n",
    "            return 0 <= pos[0] < m and 0 <= pos[1] < n\r\n",
    "        def dfs(pos):\r\n",
    "            x, y = pos\r\n",
    "            if dp[x][y] != 0:\r\n",
    "                return dp[x][y]\r\n",
    "\r\n",
    "            next_needs = list()\r\n",
    "            for next_pos in [(x+1, y), (x, y+1)]:\r\n",
    "                if is_valid_pos(next_pos):\r\n",
    "                    next_needs.append( dfs(next_pos) )\r\n",
    "            next_need = min(next_needs)\r\n",
    "            dp[x][y] = max(next_need - dungeon[x][y], 1)      \r\n",
    "            \r\n",
    "            return dp[x][y]\r\n",
    "\r\n",
    "        dfs((0, 0))\r\n",
    "        print(dp)\r\n",
    "        return dp[0][0]\r\n",
    "    \r\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\r\n",
    "        \"\"\"dfs 改写成 dp, status:continue...\"\"\"\r\n",
    "        m, n = len(dungeon), len(dungeon[0])\r\n",
    "        def is_valid_pos(pos):\r\n",
    "            return 0 <= pos[0] < m and 0 <= pos[1] < n\r\n",
    "        \r\n",
    "        dp = [ [0] * n for i in range(m)]   # hp needed to arrive destination\r\n",
    "        dp[-1][-1] = max(1-dungeon[-1][-1], 1)\r\n",
    "        for i, j in product(range(m-1, -1, -1), range(n-1, -1, -1)):\r\n",
    "            if i == m-1 and j == n-1:\r\n",
    "                continue\r\n",
    "            next_needs = list()\r\n",
    "            for next_pos in [(i+1, j), (i, j+1)]:\r\n",
    "                if is_valid_pos(next_pos):\r\n",
    "                    next_needs.append(dp[next_pos[0]][next_pos[1]])\r\n",
    "            next_need = min(next_needs)\r\n",
    "            dp[i][j] = max(next_need - dungeon[i][j], 1)\r\n",
    "        \r\n",
    "        return dp[0][0]\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        # 动态规划，从右下角开始反推\n",
    "        # dp(i,j)表示dungeon[i,j]到右下角的最小生命值\n",
    "        if len(dungeon)==0:\n",
    "            return 0\n",
    "        rows, cols = len(dungeon), len(dungeon[0])\n",
    "        dp = [[float('inf')]*(cols+1) for _ in range(rows+1)]\n",
    "        dp[rows][cols-1] = dp[rows-1][cols] = 1\n",
    "        for i in range(rows-1, -1, -1):\n",
    "            for j in range(cols-1, -1, -1):\n",
    "                tmp = min(dp[i+1][j], dp[i][j+1])\n",
    "                dp[i][j] = max(1, tmp-dungeon[i][j])\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\r\n",
    "        m, n = len(dungeon), len(dungeon[0])\r\n",
    "        INT_MAX = 2 **31\r\n",
    "        dp = [INT_MAX] * (n-1) + [1]\r\n",
    "        # dp[-1] = max(-dungeon[-1][-1], 1)\r\n",
    "        for i in reversed(range(m)):\r\n",
    "            for j in reversed(range(n)):\r\n",
    "                # print(dp)\r\n",
    "                dp[j] = max(min(dp[j:j+2])-dungeon[i][j], 1)\r\n",
    "            # print(dp)\r\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        if not dungeon or not dungeon[0]:\n",
    "            return 0\n",
    "        if len(dungeon) == 1 and len(dungeon[0])==1:\n",
    "            return 1 if dungeon[0][0] > 0 else -dungeon[0][0] + 1\n",
    "        dp = dungeon[::]\n",
    "        if dungeon[-1][-1] > 0 :\n",
    "            dp[-1][-1] = 0 \n",
    "        for i in range(len(dp)-2, -1, -1):\n",
    "            dp[i][-1] = min(dp[i][-1]+dp[i+1][-1],0)\n",
    "        for j in range(len(dp[0])-2,-1,-1):\n",
    "            dp[-1][j] = min(dp[-1][j]+dp[-1][j+1],0)\n",
    "        for i in range(len(dp)-2, -1,-1):\n",
    "            for j in range(len(dp[0])-2,-1,-1):\n",
    "                dp[i][j] = min(max(dp[i][j]+dp[i+1][j], dp[i][j]+dp[i][j+1]),0)\n",
    "        return 1- dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        \n",
    "        m = len(dungeon)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        n = len(dungeon[0])\n",
    "\n",
    "        record = [[0 for j in range(n)] for i in range(m)]\n",
    "\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if i == m - 1 and j == n - 1:\n",
    "                    record[i][j] = max(1, 1 - dungeon[i][j])\n",
    "                elif i == m - 1 and j != n - 1:\n",
    "                    record[i][j] = max(1, record[i][j + 1] - dungeon[i][j])\n",
    "                elif i != m - 1 and j == n - 1:\n",
    "                    record[i][j] = max(1, record[i + 1][j] - dungeon[i][j])\n",
    "                else:\n",
    "                    record[i][j] = max(1, min(record[i+1][j], record[i][j+1]) - dungeon[i][j])\n",
    "        return record[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        dp = copy.deepcopy(dungeon)\n",
    "        for i in range(len(dungeon) - 1, -1, -1):\n",
    "            for j in range(len(dungeon[i]) - 1, -1, -1):\n",
    "                if i == len(dungeon) - 1 and j == len(dungeon[i]) - 1:\n",
    "                    if dp[i][j] > 0:\n",
    "                        dp[i][j] = 0\n",
    "                    continue\n",
    "                if i == len(dungeon) - 1:\n",
    "                    dp[i][j] = min(0, dungeon[i][j] + dp[i][j + 1])\n",
    "                    continue\n",
    "                if j == len(dungeon[i]) - 1:\n",
    "                    dp[i][j] = min(0, dungeon[i][j] + dp[i + 1][j])\n",
    "                    continue\n",
    "                dp[i][j] = min(0, max(dungeon[i][j] + dp[i][j + 1], dungeon[i][j] + dp[i + 1][j]))\n",
    "        return 1 if dp[0][0] > 0 else 1 - dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        # \"\"\n",
    "        # dp[i][j] = min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]\n",
    "        # \"\"\n",
    "        e = 10**9\n",
    "        m,n = len(dungeon),len(dungeon[0])\n",
    "        dp = [[e for _ in range(n)] for _ in range(m)]\n",
    "        dp[-1][-1] = max(1-dungeon[-1][-1],1)\n",
    "        for i in range(m-2,-1,-1):\n",
    "            dp[i][-1] = max(1,dp[i+1][-1]-dungeon[i][-1])\n",
    "        for j in range(n-2,-1,-1):\n",
    "            dp[-1][j] = max(1,dp[-1][j+1]-dungeon[-1][j])  \n",
    "        for i in range(m-2,-1,-1):\n",
    "            for j in range(n-2,-1,-1):\n",
    "                dp[i][j] = max(1,min(dp[i+1][j],dp[i][j+1])-dungeon[i][j])\n",
    "        print(dp)        \n",
    "        return dp[0][0]        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "\n",
    "        m=len(dungeon)\n",
    "        n=len(dungeon[0])\n",
    "        # print(float(\"inf\"))\n",
    "        dp=[[float(\"inf\") for i in range(n+1)] for j in range(m+1)]\n",
    "        # print(m,n)\n",
    "        dp[m-1][n] = dp[m][n-1] = 1\n",
    "        for i in dp:\n",
    "            print(i)\n",
    "        print('________________')\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n - 1,-1, -1):\n",
    "                print(i,j)\n",
    "\n",
    "                print('dungeon[i][j]',dungeon[i][j])\n",
    "\n",
    "                print('dp[i + 1][j]',dp[i + 1][j])\n",
    "                print('dp[i][j + 1]',dp[i][j + 1])\n",
    "                minn = min(dp[i + 1][j], dp[i][j + 1])\n",
    "                print('minn',minn)\n",
    "                dp[i][j] = max(minn - dungeon[i][j], 1)\n",
    "                print('dp[i][j]',dp[i][j])\n",
    "                print('+++++++++++')\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        n, m = len(dungeon), len(dungeon[0])\n",
    "        BIG = 10**9\n",
    "        dp = [[BIG] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[n][m - 1] = dp[n - 1][m] = 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                minn = min(dp[i + 1][j], dp[i][j + 1])\n",
    "                dp[i][j] = max(minn - dungeon[i][j], 1)\n",
    "\n",
    "        return dp[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon):\n",
    "        n = len(dungeon[0])\n",
    "        need = [2**31] * (n-1) + [1]\n",
    "        for row in dungeon[::-1]:\n",
    "            for j in range(n)[::-1]:\n",
    "                need[j] = max(min(need[j:j+2]) - row[j], 1)\n",
    "        return need[0]\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        m = len(dungeon); n = len(dungeon[0])\n",
    "        dp = [[10**10]*(n+1) for _ in range(m+1)]\n",
    "        dp[m][n-1] = 1\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                dp[i][j] = max(1,min(dp[i+1][j],dp[i][j+1])-dungeon[i][j])\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        d = dungeon\n",
    "        n,m = len(d),len(d[0])\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(m-1,-1,-1):\n",
    "                # print('\\n'.join([str(di) for di in d]))\n",
    "                # print(i,j)\n",
    "                # print()\n",
    "                if i==n-1 and j==m-1:\n",
    "                    continue\n",
    "                elif i==n-1:\n",
    "                    d[i][j]=min(d[i][j], d[i][j]+d[i][j+1])\n",
    "                    # print(d[i][j], d[i][j+1])\n",
    "                elif j==m-1:\n",
    "                    d[i][j]=min(d[i][j], d[i][j]+d[i+1][j])\n",
    "                else:\n",
    "                    d[i][j]=min(d[i][j], d[i][j] + max(d[i][j+1],d[i+1][j]))\n",
    "                \n",
    "\n",
    "        # print('\\n'.join([str(di) for di in d]))\n",
    "        return 1-min(d[0][0],0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        m, n = len(dungeon), len(dungeon[0])\n",
    "        def check(t):\n",
    "            q = {(0, 0): t}\n",
    "            while q:\n",
    "                tmp = dict()\n",
    "                for (i, j), k in q.items():\n",
    "                    k += dungeon[i][j]\n",
    "                    if k > 0:\n",
    "                        if i == m - 1 and j == n - 1:\n",
    "                            return True\n",
    "                        if i + 1 < m:\n",
    "                            if (i + 1, j) not in tmp: tmp[(i + 1, j)] = k\n",
    "                            else: tmp[(i + 1, j)] = max(k, tmp[(i + 1, j)])\n",
    "                        if j + 1 < n:\n",
    "                            if (i, j + 1) not in tmp: tmp[(i, j + 1)] = k\n",
    "                            else: tmp[(i, j + 1)] = max(k, tmp[(i, j + 1)])\n",
    "                q = tmp\n",
    "            return False\n",
    "        lo, hi = 1, 1000 * (m + n - 1) + 1\n",
    "        while lo < hi:\n",
    "            mid = (lo + hi) // 2\n",
    "            if check(mid):\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return hi\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        m,n = len(dungeon), len(dungeon[0])\n",
    "        memo = [[-1]*n for _ in range(m)]\n",
    "        return self.dp(dungeon, 0, 0, memo)\n",
    "\n",
    "    def dp(self, grid,i,j, memo):\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        if i==m-1 and j==n-1:\n",
    "            if grid[i][j]>0:\n",
    "                return 1\n",
    "            else:\n",
    "                return -grid[i][j]+1\n",
    "        if i==m or j==n:\n",
    "            return float(\"inf\")\n",
    "        if memo[i][j] != -1:\n",
    "            return memo[i][j]\n",
    "        res = min(self.dp(grid, i+1,j, memo), self.dp(grid,i,j+1, memo))-grid[i][j]\n",
    "        if res>0:\n",
    "            memo[i][j] = res\n",
    "        else:\n",
    "            memo[i][j] = 1\n",
    "        return memo[i][j]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.dungeon: Optional[List[List[int]]] = None\n",
    "        self.dp: Optional[List[List[int]]] = None\n",
    "\n",
    "    def ValidPos(self, row, col):\n",
    "        return 0 <= row < len(self.dungeon) and 0 <= col < len(self.dungeon[row])\n",
    "\n",
    "    def SavePrincess(self, row, col) -> int:\n",
    "        if not self.ValidPos(row, col):\n",
    "            return 0xFFFFFFFF\n",
    "\n",
    "        if self.dp[row][col] != 0:\n",
    "            return self.dp[row][col]\n",
    "\n",
    "        if row == len(self.dungeon) - 1 and col == len(self.dungeon[0]) - 1:\n",
    "            self.dp[row][col] = max(self.dungeon[row][col] * -1, 0) + 1\n",
    "            return self.dp[row][col]\n",
    "\n",
    "        rowRight, colRight = row, col + 1\n",
    "        right = self.SavePrincess(rowRight, colRight)\n",
    "        rowDown, colDown = row + 1, col\n",
    "        down = self.SavePrincess(rowDown, colDown)\n",
    "\n",
    "        resNext = min(right, down)\n",
    "        res = resNext - self.dungeon[row][col]\n",
    "        self.dp[row][col] = max(res, 1)\n",
    "        return self.dp[row][col]\n",
    "\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        self.dungeon = dungeon\n",
    "        self.dp = [[0 for j in i] for i in self.dungeon]\n",
    "        res = self.SavePrincess(0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        \n",
    "        for m in range(len(dungeon) - 1, -1, -1):\n",
    "            for n in range(len(dungeon[0]) - 1, -1, -1):\n",
    "                if m == len(dungeon) - 1 and n == len(dungeon[0]) - 1:\n",
    "                    if dungeon [m][n] < 0:\n",
    "                        dungeon [m][n] = abs(dungeon [m][n]) + 1\n",
    "                    else:\n",
    "                        dungeon [m][n] = 1\n",
    "\n",
    "\n",
    "\n",
    "                if m < len(dungeon) - 1 and n < len(dungeon[0]) - 1:\n",
    "                    dungeon [m][n] = min(dungeon[m + 1][n], dungeon[m][n + 1]) - dungeon [m][n]\n",
    "                    if dungeon[m][n] <= 0:\n",
    "                        dungeon[m][n] = 1\n",
    "                \n",
    "                if m == len(dungeon) - 1 and n < len(dungeon[0]) - 1:\n",
    "                    dungeon [m][n] = dungeon[m][n + 1] - dungeon [m][n]\n",
    "                    if dungeon[m][n] <= 0:\n",
    "                        dungeon[m][n] = 1\n",
    "                \n",
    "                if n == len(dungeon[0]) - 1 and m < len(dungeon) - 1:\n",
    "                    dungeon [m][n] = dungeon[m + 1][n] - dungeon [m][n]\n",
    "                    if dungeon[m][n] <= 0:\n",
    "                        dungeon[m][n] = 1\n",
    "\n",
    "        return dungeon[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        m=len(dungeon)\n",
    "        n=len(dungeon[0])\n",
    "        dp=[[0] * n for i in range(m)]\n",
    "        dp[-1][-1]=max(1,1-dungeon[-1][-1])\n",
    "        for i in range(m-2,-1,-1):\n",
    "            dp[i][-1]=max(1,dp[i+1][-1]-dungeon[i][-1])\n",
    "        for j in range(n-2,-1,-1):\n",
    "            dp[-1][j]=max(1,dp[-1][j+1]-dungeon[-1][j])\n",
    "        for i in range(m-2,-1,-1):\n",
    "            for j in range(n-2,-1,-1):\n",
    "                dp[i][j]=max(1,min(dp[i+1][j]-dungeon[i][j],dp[i][j+1]-dungeon[i][j]))\n",
    "        return dp[0][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        # 倒序dp\n",
    "        m, n = len(dungeon), len(dungeon[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[-1][-1] = max(0, -dungeon[-1][-1])\n",
    "        for i in range(m-2,-1,-1):\n",
    "            dp[i][-1] = max(0, dp[i+1][-1] - dungeon[i][-1])\n",
    "        for j in range(n-2,-1,-1):\n",
    "            dp[-1][j] = max(0, dp[-1][j+1] - dungeon[-1][j])\n",
    "        for i in range(m-2,-1,-1):\n",
    "            for j in range(n-2,-1,-1):\n",
    "                dp[i][j] = max(0, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])\n",
    "        return dp[0][0] + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        x = len(dungeon)\n",
    "        y = len(dungeon[0])\n",
    "        mem = [[-1 for _ in range(y)] for _ in range(x)]\n",
    "\n",
    "        def dp(matrix, i, j):\n",
    "            if i >= x or j >= y:\n",
    "                return float('inf')\n",
    "            \n",
    "            if i == x - 1 and j == y - 1:\n",
    "                return 1 if matrix[i][j] >= 0 else 1 - matrix[i][j]\n",
    "\n",
    "            if mem[i][j] != -1:\n",
    "                return mem[i][j]\n",
    "\n",
    "            res = min(dp(matrix, i, j+1), dp(matrix, i+1, j)) - matrix[i][j]\n",
    "            mem[i][j] = 1 if res <= 0 else res\n",
    "\n",
    "            return mem[i][j]\n",
    "\n",
    "        return dp(dungeon, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        m, n = len(dungeon), len(dungeon[0])\n",
    "        dp = [[float(\"inf\") for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        dp[m - 1][n - 1] = 1 - dungeon[m - 1][n - 1] if dungeon[m - 1][n - 1] <= 0 else 1\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            tmp = dp[m - 1][i + 1] - dungeon[m - 1][i]\n",
    "            if tmp > 0:\n",
    "                dp[m - 1][i] = tmp\n",
    "            else:\n",
    "                dp[m - 1][i] = 1\n",
    "        \n",
    "        for i in range(m - 2, -1, -1):\n",
    "            tmp = dp[i + 1][n - 1] - dungeon[i][n - 1]\n",
    "            if tmp > 0:\n",
    "                dp[i][n - 1] = tmp\n",
    "            else:\n",
    "                dp[i][n - 1] = 1\n",
    "        \n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                dp[i][j] = max(min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j], 1)\n",
    "        \n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        h = len(dungeon)\n",
    "        l = len(dungeon[0])\n",
    "        dp = [[-10000 if i == l or j == h else 0 for i in range(l + 1)] for j in range(h + 1)]\n",
    "        dp[h - 1][l - 1] = dungeon[h - 1][l - 1] if dungeon[h - 1][l - 1] < 0 else 0\n",
    "        for i in range(h - 1, -1, -1):\n",
    "            for j in range(l - 1, -1, -1):\n",
    "                if i == h - 1 and j == l - 1:\n",
    "                    continue\n",
    "                dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]) + dungeon[i][j]\n",
    "                if dp[i][j] > 0:\n",
    "                    dp[i][j] = 0\n",
    "        print(dp)\n",
    "        if dp[0][0] <= 0:\n",
    "            return -dp[0][0] + 1\n",
    "        else:\n",
    "            return 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        m = len(dungeon)\n",
    "        n = len(dungeon[0])\n",
    "        dp = [[[0] for j in range(n)] for i in range(m)]\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                #print(dp)\n",
    "                if i == m-1 and j == n-1:\n",
    "                    dp[i][j] = max(1, 1-dungeon[i][j])\n",
    "                elif i == m-1:\n",
    "                    dp[i][j] = max(1, dp[i][j+1]-dungeon[i][j])\n",
    "                elif j == n-1:\n",
    "                    dp[i][j] = max(1, dp[i+1][j]-dungeon[i][j])\n",
    "                else:\n",
    "                    dp[i][j] = max(1, min(dp[i][j+1]-dungeon[i][j], dp[i+1][j]-dungeon[i][j]))\n",
    "\n",
    "        return dp[0][0]\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        m = len(dungeon)\n",
    "        n = len(dungeon[0])\n",
    "        f = [[[0] for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if i == m - 1 and j == n - 1:\n",
    "                    f[i][j] = max(1, 1 - dungeon[i][j])\n",
    "                elif i == m - 1:\n",
    "                    f[i][j] = max(1, f[i][j + 1] - dungeon[i][j])\n",
    "                elif j == n - 1:\n",
    "                    f[i][j] = max(1, f[i + 1][j] - dungeon[i][j])\n",
    "                else:\n",
    "                    f[i][j] = max(1, min(f[i][j + 1], f[i + 1][j]) - dungeon[i][j])\n",
    "        \n",
    "        return f[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        ##如果定义是从起点走到某个点的最小生命值，那么当左边和上边的值相等时，并不能决定选择哪条路，还需要知道此时的血量\n",
    "        ##如果定义是某点到终点的初始生命值，那么相等时是可以一起选的\n",
    "        memo=dict()\n",
    "        m,n=len(dungeon),len(dungeon[0])\n",
    "\n",
    "        def dp(i,j):\n",
    "            if i==m-1 and j==n-1:\n",
    "                return 1 if dungeon[i][j]>=0 else -dungeon[i][j]+1\n",
    "            if i==m or j==n:\n",
    "                return inf\n",
    "            key=str(i)+\",\"+str(j)\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "\n",
    "            res=min(dp(i,j+1),dp(i+1,j))-dungeon[i][j]\n",
    "            memo[key]= res if res>0 else 1\n",
    "            return memo[key]\n",
    "        return dp(0,0)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import copy\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        m,n = len(dungeon) , len(dungeon[0])\n",
    "        mn = max(m,n)\n",
    "        a ,dp = [],[]\n",
    "        for i in range(mn):\n",
    "            a += [[]]\n",
    "        for j in range (mn):\n",
    "            dp += [copy.deepcopy(a)]\n",
    "        #dp[i][j]是0血走到i,j能保存的最大hp和需要的初始hp\n",
    "        dp[0][0]+=[[dungeon[0][0],max(1,1-dungeon[0][0])]]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 and j == 0:\n",
    "                    continue\n",
    "                elif i == 0:\n",
    "                    #print(dp[i])\n",
    "                    dp[i][j] += [[dp[i][j-1][0][0] + dungeon[i][j],max(dp[i][j-1][0][1], 1 - dp[i][j-1][0][0] - dungeon[i][j])]]\n",
    "                elif j == 0:\n",
    "                    #print(i,j)\n",
    "                    dp[i][j] += [[dp[i-1][j][0][0] + dungeon[i][j],max(dp[i-1][j][0][1], 1 - dp[i-1][j][0][0] - dungeon[i][j])]]\n",
    "                else:\n",
    "                    #print(dp)\n",
    "                    u,v = len(dp[i-1][j]), len(dp[i][j-1])\n",
    "                    for s in range(u):\n",
    "                        dp[i][j] += [[dp[i-1][j][s][0] + dungeon[i][j],max(dp[i-1][j][s][1], 1 - dp[i-1][j][s][0] - dungeon[i][j])]]\n",
    "                    for t in range(v):\n",
    "                        dp[i][j] += [[dp[i][j-1][t][0] + dungeon[i][j],max(dp[i][j-1][t][1], 1 - dp[i][j-1][t][0] - dungeon[i][j])]]\n",
    "                    dp[i][j] = sorted(dp[i][j],key=lambda x: (5*x[1]-x[0]))\n",
    "                    l = int(len(dp[i][j])*0.5)\n",
    "                    if l > 10:\n",
    "                        dp[i][j] = dp[i][j][:l]\n",
    "                    dp[i-1][j-1] = []\n",
    "        #print(dp[m-1][n-1])\n",
    "        ll = len(dp[m-1][n-1])\n",
    "        return min(dp[m-1][n-1][k][1] for k in range(ll))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\n",
    "        m, n = len(dungeon), len(dungeon[0])\n",
    "        \n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if i == m - 1 and j == n - 1:\n",
    "                return max(-dungeon[i][j], 0)\n",
    "            if i >= m or j >= n:\n",
    "                return inf\n",
    "            res = inf\n",
    "            if i < m - 1:\n",
    "                res = min(res, f(i+1, j) - dungeon[i][j])\n",
    "            if j < n - 1:\n",
    "                res = min(res, f(i, j+1) - dungeon[i][j])\n",
    "            return max(res, 0)\n",
    "\n",
    "        return max(f(0, 0), 0) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:\r\n",
    "        m,n = len(dungeon), len(dungeon[0])\r\n",
    "        import functools\r\n",
    "        @functools.lru_cache(None)\r\n",
    "        def dfs(x, y):\r\n",
    "            ret = []\r\n",
    "            for dx, dy in [(0 , 1), (1, 0)]:\r\n",
    "                if x+dx < m and y+dy < n:\r\n",
    "                    ret.append(dfs(x+dx, y+dy))\r\n",
    "            if ret:\r\n",
    "                return max(min(ret) - dungeon[x][y], 1)\r\n",
    "            else:\r\n",
    "                return max(1, 1 - dungeon[x][y])\r\n",
    "        return dfs(0, 0)\r\n",
    "\r\n",
    "        \r\n",
    "        \r\n",
    "\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
